{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sliding Window Maximum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSlidingWindow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #滑动窗口最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>，有一个大小为&nbsp;<code>k</code><em>&nbsp;</em>的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 <code>k</code>&nbsp;个数字。滑动窗口每次只向右移动一位。</p>\n",
    "\n",
    "<p>返回 <em>滑动窗口中的最大值 </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,3,-1,-3,5,3,6,7], k = 3\n",
    "<b>输出：</b>[3,3,5,5,6,7]\n",
    "<b>解释：</b>\n",
    "滑动窗口的位置                最大值\n",
    "---------------               -----\n",
    "[1  3  -1] -3  5  3  6  7       <strong>3</strong>\n",
    " 1 [3  -1  -3] 5  3  6  7       <strong>3</strong>\n",
    " 1  3 [-1  -3  5] 3  6  7      <strong> 5</strong>\n",
    " 1  3  -1 [-3  5  3] 6  7       <strong>5</strong>\n",
    " 1  3  -1  -3 [5  3  6] 7       <strong>6</strong>\n",
    " 1  3  -1  -3  5 [3  6  7]      <strong>7</strong>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1], k = 1\n",
    "<b>输出：</b>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sliding-window-maximum](https://leetcode.cn/problems/sliding-window-maximum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sliding-window-maximum](https://leetcode.cn/problems/sliding-window-maximum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,-1,-3,5,3,6,7]\\n3', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        class monotonicQue:\n",
    "            def __init__(self):\n",
    "                self.maxq = []\n",
    "            def push(self, n):\n",
    "                while self.maxq and self.maxq[-1] < n:\n",
    "                    self.maxq.pop()\n",
    "                self.maxq.append(n)\n",
    "            def max(self):\n",
    "                return self.maxq[0]\n",
    "            def pop(self, n):\n",
    "                if n == self.maxq[0]:\n",
    "                    self.maxq.pop(0)\n",
    "\n",
    "        window = monotonicQue()\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if i < k-1:\n",
    "                window.push(nums[i])\n",
    "            else:\n",
    "                window.push(nums[i])\n",
    "                res.append(window.max())\n",
    "                window.pop(nums[i-k+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        max_list = []\n",
    "        temp_list = nums[:k]\n",
    "        max_list.append(max(temp_list))\n",
    "        for i in nums[k:]:\n",
    "            temp_list.pop(0)\n",
    "            temp_list.append(i)\n",
    "            max_list.append(max(temp_list))\n",
    "        return max_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class MonotonicQueue(deque):\n",
    "    def __init__(self):\n",
    "        self.queue = deque()\n",
    "\n",
    "    def push(self, num):\n",
    "        while self.queue and num > self.queue[-1]:\n",
    "            self.queue.pop()\n",
    "        self.queue.append(num)\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not nums or k <= 0: return []\n",
    "        res = []\n",
    "        mq = MonotonicQueue()\n",
    "        for i in range(0, k - 1):\n",
    "            mq.push(nums[i])\n",
    "        for i in range(k - 1, len(nums)):\n",
    "            mq.push(nums[i])\n",
    "            res.append(mq.queue[0])\n",
    "            if nums[i - k + 1] == mq.queue[0]: mq.queue.popleft()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class monoQueue:\n",
    "    def __init__(self):\n",
    "        self.deque = []\n",
    "        \n",
    "    def enqueue(self, x):\n",
    "        count = 0\n",
    "        while self.deque and self.deque[-1][0] < x:\n",
    "            count += self.deque[-1][1] + 1\n",
    "            self.deque.pop(-1)\n",
    "        self.deque.append([x, count])\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.deque[0][1] == 0:\n",
    "            self.deque.pop(0)\n",
    "        else:\n",
    "            self.deque[0][1] -= 1\n",
    "            \n",
    "    def maximum(self):\n",
    "        if self.deque:\n",
    "            return self.deque[0][0]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        mq = monoQueue()\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            mq.enqueue(nums[i])\n",
    "        res.append(mq.maximum())\n",
    "        for i in range(k, n):\n",
    "            mq.dequeue()\n",
    "            mq.enqueue(nums[i])\n",
    "            res.append(mq.maximum())\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if len(nums)==0:\n",
    "            return []\n",
    "        res=[]\n",
    "        if len(nums)<=k:\n",
    "            return [max(nums)]\n",
    "        for i in range(len(nums)-k+1):\n",
    "            res.append(max(nums[i:i+k]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.r=0\n",
    "        self.l=0\n",
    "    def maxSlidingWindow(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        \n",
    "        res =[]\n",
    "        arr =[0]\n",
    "        def add(arr):\n",
    "            self.r +=1\n",
    "            while len(arr)!=0 and (nums[arr[-1]] <= nums[self.r]) :\n",
    "                arr.pop(-1)\n",
    "            arr.append(self.r)\n",
    "            \n",
    "            #print(2,arr)\n",
    "        def rm(arr):\n",
    "            if self.l == arr[0]:\n",
    "                arr.pop(0)\n",
    "            self.l +=1        \n",
    "            #print(1,arr)\n",
    "        for _ in range(k-1): \n",
    "            add(arr)\n",
    "        res.append(nums[arr[0]])\n",
    "        while self.r< len(nums)-1:\n",
    "            print(self.r)\n",
    "            add(arr)\n",
    "            rm(arr)\n",
    "            res.append(nums[arr[0]])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        window, res = [], []\n",
    "        for i, x in enumerate(nums):\n",
    "            if i >= k and window[0] <= i - k:\n",
    "                window.pop(0)\n",
    "            while window and nums[window[-1]] <= x:\n",
    "                window.pop()\n",
    "            window.append(i)\n",
    "            if i >= k - 1:\n",
    "                res.append(nums[window[0]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        # brute force solution\n",
    "        n = len(nums)\n",
    "        if n * k == 0: # n = 0 or k = 0 \n",
    "            return []  # 8 6 \n",
    "\n",
    "        max_ = []\n",
    "        for i in range(n - k + 1):\n",
    "            max_.append(max(nums[i:i + k]))\n",
    "        return max_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        '''\n",
    "        难点在于线性时间\n",
    "        使用动态规划法，定义两个状态\n",
    "        dpl[i]: 第i个元素到块左边界所有元素的最大值\n",
    "            dpl[i] = max(dpl[i-1], nums[i]) or \n",
    "            dpl[i] = nums[i] 此时i%k==0 位于块的起始位置 \n",
    "        dpr[i]: 第i个元素到块右边界所有元素的最大值\n",
    "            dpr[i] = max(dpr[i+1], nums[i]) or \n",
    "            dpr[i] = nums[i] 此时i+1 %k==0 位于快的结束位置\n",
    "        滑动窗[i,i+k-1]上的最大值为max(dpr[i], dpl[i+k-1])\n",
    "        '''\n",
    "\n",
    "        if  not nums or k==0:\n",
    "            return []\n",
    "\n",
    "        if k== 1:\n",
    "            return nums\n",
    "        \n",
    "        n = len(nums)\n",
    "\n",
    "        # 初始化状态\n",
    "        dpl = [0] * n\n",
    "        dpl[0] = nums[0] \n",
    "        dpr = [0] * n\n",
    "        dpr[n-1] = nums[n-1]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if i % k == 0:\n",
    "                dpl[i] = nums[i]\n",
    "            else:\n",
    "                dpl[i] = max(dpl[i-1], nums[i])\n",
    "            \n",
    "            j = n-1-i\n",
    "            if (j+1) % k == 0:\n",
    "                dpr[j] = nums[j]\n",
    "            else:\n",
    "                dpr[j] = max(dpr[j+1], nums[j])\n",
    "        \n",
    "        result = []\n",
    "        for i in range(n-k+1):\n",
    "            result.append(max(dpr[i], dpl[i+k-1]))\n",
    "        return result\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if(not nums or not k):\n",
    "            return []\n",
    "        length = len(nums)\n",
    "        if(length <= k):\n",
    "            return [max(nums)]\n",
    "        count = 0\n",
    "        res = []\n",
    "        new = []\n",
    "        left = []\n",
    "        right = []\n",
    "        temp = []\n",
    "        for num in nums:\n",
    "            if(count == k):\n",
    "                new.append(temp)\n",
    "                temp = []\n",
    "                count = 0\n",
    "            temp.append(num)\n",
    "            count += 1\n",
    "        new.append(temp)\n",
    "        for each in new:\n",
    "            Max = each[0]\n",
    "            for num in each:\n",
    "                Max = max(Max, num)\n",
    "                left.append(Max)\n",
    "        for each in new[::-1]:\n",
    "            Max = each[-1]\n",
    "            for num in each[::-1]:\n",
    "                Max = max(Max, num)\n",
    "                right.append(Max)\n",
    "        right = right[::-1]\n",
    "        for i in range(length-k+1):\n",
    "            res.append(max(left[i+k-1], right[i]))\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n * k == 0:\n",
    "            return []\n",
    "        if n==1:\n",
    "            return nums\n",
    "\n",
    "        ## 使用优先级队列(大顶堆)\n",
    "        res = []\n",
    "        heap = []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(heap, -nums[i])\n",
    "        res.append(-heap[0])        \n",
    "        for i in range(k, n):\n",
    "            heap.remove(-nums[i-k])\n",
    "            heapq.heapify(heap)\n",
    "            heapq.heappush(heap, -nums[i])\n",
    "            res.append(-heap[0])\n",
    "        return res\n",
    "        \n",
    "        # 使用双端队列存储索引\n",
    "        # dq = deque()\n",
    "        # def clean_deque(i):\n",
    "        #     # 删除不是当前滑动窗口的索引\n",
    "        #     if dq and dq[0] == i - k:\n",
    "        #         dq.popleft()\n",
    "        #     # 移除比当前元素小的元素，他们不可能是窗口中的最大值\n",
    "        #     while dq and nums[i] > nums[dq[-1]]:\n",
    "        #         dq.pop()\n",
    "        \n",
    "        # res = []\n",
    "        # maxid = 0\n",
    "        # # 处理前k个元素\n",
    "        # for i in range(k):\n",
    "        #     clean_deque(i)\n",
    "        #     dq.append(i)\n",
    "        #     if nums[i] > nums[maxid]:\n",
    "        #         maxid = i\n",
    "        # res.append(nums[maxid])\n",
    "        # for i in range(k, n):\n",
    "        #     clean_deque(i)\n",
    "        #     dq.append(i)\n",
    "        #     res.append(nums[dq[0]])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not len(nums) * k:\n",
    "            return []\n",
    "\n",
    "        ret = []\n",
    "        for i in range(0, len(nums) - k + 1):\n",
    "            hp = [-x for x in nums[i:i+k]]\n",
    "            heapq.heapify(hp)\n",
    "            ret.append(-hp[0])\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i in range(n-k+1):\n",
    "            res.append(max(nums[i:i+k]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        q=[]\n",
    "        res=[]\n",
    "        nums=[-w for w in nums]\n",
    "        for i in range(k):\n",
    "            heapq.heappush(q,nums[i])\n",
    "        res.append(q[0]*-1)\n",
    "        for i in range(k,len(nums)):\n",
    "            q.remove(nums[i-k])\n",
    "            heapq.heappush(q,nums[i])\n",
    "            heapq.heapify(q)\n",
    "            res.append(q[0]*-1)\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "\n",
    "        ans = [0] * (len(nums) - k + 1)\n",
    "        in_sliding_window = {}\n",
    "        for i in range(k):\n",
    "            if nums[i] in in_sliding_window:\n",
    "                in_sliding_window[nums[i]] += 1\n",
    "            else:\n",
    "                in_sliding_window[nums[i]] = 1\n",
    "        heap = [-nums[i] for i in range(k)]\n",
    "        heapq.heapify(heap)\n",
    "        ans[0] = -heap[0]\n",
    "\n",
    "        # print([-i for i in nums])\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            # print(i - k, nums[i - k], heap, ans)\n",
    "            heapq.heappush(heap, -nums[i])\n",
    "            if nums[i] in in_sliding_window:\n",
    "                in_sliding_window[nums[i]] += 1\n",
    "            else:\n",
    "                in_sliding_window[nums[i]] = 1\n",
    "\n",
    "            in_sliding_window[nums[i - k]] -= 1\n",
    "\n",
    "            x = -heap[0]\n",
    "            while in_sliding_window[x] == 0:\n",
    "                heapq.heappop(heap)\n",
    "                x = -heap[0]\n",
    "            else:\n",
    "                ans[i - k + 1] = x\n",
    "\n",
    "        return ans\n",
    "\"\"\"\n",
    "[1,3,-1,-3,5,3,6,7]\n",
    "3\n",
    "[]\n",
    "0\n",
    "[1,-1]\n",
    "1\n",
    "[9,10,9,-7,-4,-8,2,-6]\n",
    "5\n",
    "\"\"\"\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\n",
    "import heapq\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # Solution 1: double ended queue\n",
    "    # def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "    #     res = []\n",
    "    #     deq = deque()\n",
    "    #     for idx, num in enumerate(nums):\n",
    "    #         while deq and num > nums[deq[-1]]:\n",
    "    #             deq.pop()\n",
    "    #         deq.append(idx)\n",
    "    #         if deq and idx - deq[0] >= k:\n",
    "    #             deq.popleft()\n",
    "    #         if idx >= k - 1:\n",
    "    #             res.append(nums[deq[0]])\n",
    "    #     return res\n",
    "\n",
    "    # Solution 2: heap\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        res, counter, heap = [], collections.Counter(), []\n",
    "        for idx, num in enumerate(nums):\n",
    "            heapq.heappush(heap, -num)\n",
    "            counter[num] += 1\n",
    "            if idx >= k - 1:\n",
    "                while counter[-heap[0]] == 0:\n",
    "                    heapq.heappop(heap)\n",
    "                res.append(-heap[0])\n",
    "                counter[nums[idx - k + 1]] -= 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums or not k:\n",
    "            nums\n",
    "        ans = {}\n",
    "        L = len(nums)\n",
    "        # 找位置0的数的边界\n",
    "        cur = nums[0]\n",
    "        cur_p = 0\n",
    "        left = 0\n",
    "        right = cur_p\n",
    "        \n",
    "        while right < L and nums[right] <= cur:\n",
    "            right += 1\n",
    "        right -= 1\n",
    "        i = 0\n",
    "        while i < L:\n",
    "#             print(i,nums[i],'==============')\n",
    "            if i:  # 如果i为0，就不用执行if语句内的代码了\n",
    "                if nums[i-1] > nums[i]:  # 前一个数大\n",
    "                    left = i  # 左边界即为自身\n",
    "                    # 从i开始找nums[i]的右边界\n",
    "                    right = i\n",
    "                    while right < L and nums[right] <= nums[i]:\n",
    "                        right += 1\n",
    "                    right -= 1\n",
    "                if nums[i-1] < nums[i]:  # 前一个数小\n",
    "                    # 在前一个数的左边界外找nums[i]的左边界\n",
    "                    while left >= 0 and nums[left] <= nums[i]:\n",
    "                        left -= 1\n",
    "                    left += 1\n",
    "                    # 从i开始找nums[i]的右边界\n",
    "                    right = i\n",
    "                    while right < L and nums[right] <= nums[i]:\n",
    "                        right += 1\n",
    "                    right -= 1\n",
    "                if nums[i-1] == nums[i]:\n",
    "                    pass  # 左右边界和nums[i-1]的左右边界相同\n",
    "#             print(left,right)\n",
    "            left_b = max(left,i-k+1)\n",
    "            right_b = min(right,i+k-1)\n",
    "#             print(left_b,right_b)\n",
    "\n",
    "            for time in range(left_b,left_b +right_b-left_b+1 - k + 1):\n",
    "                if time not in ans:\n",
    "                    ans[time] = nums[i]\n",
    "#             print(ans)\n",
    "            i += 1\n",
    "        return [v for v in ans.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n * k == 0:\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return nums\n",
    "        left = [0] * n\n",
    "        left[0] = nums[0]\n",
    "        right = [0] * n\n",
    "        right[n-1] = nums[n-1]\n",
    "        for i in range(1,n):\n",
    "            if i % k == 0:\n",
    "                left[i] = nums[i]\n",
    "            else:\n",
    "                left[i] = max(left[i - 1], nums[i])\n",
    "            j = n - i -1\n",
    "            if (j + 1) % k == 0:\n",
    "                right[j] = nums[j]\n",
    "            else:\n",
    "                right[j] = max(right[j+1],nums[j])\n",
    "\n",
    "        output = []\n",
    "        for i in range(n - k + 1):\n",
    "            output.append(max(left[i + k - 1], right[i]))\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        return self._deque(nums, k)\n",
    "\n",
    "    # O(n), O(k)\n",
    "    def _deque(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums or not k: return list()\n",
    "        dq, res = deque(), list()\n",
    "        for right,val in enumerate(nums):\n",
    "            while dq and nums[dq[-1]] <= val:\n",
    "                dq.pop()\n",
    "            dq.append(right)\n",
    "            if dq[0] < right - k + 1:\n",
    "                dq.popleft()\n",
    "            if right >= k - 1: res.append(nums[dq[0]])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        # base cases\n",
    "        n = len(nums)\n",
    "        if n * k == 0:\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return nums\n",
    "        \n",
    "        def clean_deque(i):\n",
    "            # remove indexes of elements not from sliding window\n",
    "            if deq and deq[0] == i - k:\n",
    "                deq.popleft()\n",
    "                \n",
    "            # remove from deq indexes of all elements \n",
    "            # which are smaller than current element nums[i]\n",
    "            while deq and nums[i] > nums[deq[-1]]:\n",
    "                deq.pop()\n",
    "        \n",
    "        # init deque and output\n",
    "        deq = deque()\n",
    "        max_idx = 0\n",
    "        for i in range(k):\n",
    "            clean_deque(i)\n",
    "            deq.append(i)\n",
    "            # compute max in nums[:k]\n",
    "            if nums[i] > nums[max_idx]:\n",
    "                max_idx = i\n",
    "        output = [nums[max_idx]]\n",
    "        \n",
    "        # build output\n",
    "        for i in range(k, n):\n",
    "            clean_deque(i)          \n",
    "            deq.append(i)\n",
    "            output.append(nums[deq[0]])\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        N = len(nums)\n",
    "        left = [0]*N\n",
    "        right = [0]*N\n",
    "        # finish left\n",
    "        for i in range(N):\n",
    "            if i%k == 0:\n",
    "                block_index = i//k\n",
    "                max_val = nums[block_index*k]\n",
    "            max_val = max(max_val, nums[i])\n",
    "            left[i] = max_val\n",
    "\n",
    "        max_val = nums[-1]\n",
    "        for i in range(N-1, -1, -1):\n",
    "            if i%k == k-1:\n",
    "                block_index = i//k\n",
    "                max_val = nums[block_index*k+k-1]\n",
    "            max_val = max(max_val, nums[i])\n",
    "            right[i] = max_val\n",
    "        print(left,right)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(N-k+1):\n",
    "            res.append(max(left[i+k-1], right[i]))\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        left = list(range(n))\n",
    "        for i in range(n):\n",
    "            if i % k == 0:\n",
    "                left[i] = nums[i]\n",
    "            else:\n",
    "                left[i] = max(nums[i], left[i-1])\n",
    "\n",
    "\n",
    "        right = list(range(n))\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i == n-1 or i % k == k - 1:\n",
    "                right[i] = nums[i]\n",
    "            else:\n",
    "                right[i] = max(nums[i], right[i+1])\n",
    "\n",
    "        output = []\n",
    "        for i in range(n-k+1):\n",
    "            if i % k == 0:\n",
    "                output.append(right[i])\n",
    "\n",
    "            else:\n",
    "                if i == 3:\n",
    "                    print(i, i+k-1)\n",
    "                    print(max(right[i], left[i+k-1]))\n",
    "                output.append(max(right[i], left[i+k-1]))\n",
    "\n",
    "\n",
    "        return output\n",
    "\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k == 1:\n",
    "            return nums\n",
    "        stack = deque()\n",
    "        for i in range(k):\n",
    "            stack.append((nums[i], i))\n",
    "        maxi = -float('inf')\n",
    "        maxi_idx = -1\n",
    "        for i in range(len(stack)):\n",
    "            if stack[i][0] >= maxi:\n",
    "                maxi = stack[i][0]\n",
    "                maxi_idx = i\n",
    "        while stack[0][1] < maxi_idx:\n",
    "            stack.popleft()\n",
    "        res = [stack[0][0]]\n",
    "        for i in range(1, len(nums) - k + 1):\n",
    "            stack.append((nums[k + i - 1], k + i - 1))\n",
    "            if i <= stack[0][1] and stack[0][0] > stack[-1][0]:\n",
    "                res.append(stack[0][0])\n",
    "            else:\n",
    "                stack.popleft()\n",
    "                maxi = -float('inf')\n",
    "                maxi_idx = -1\n",
    "                for j in range(len(stack)):\n",
    "                    if stack[j][0] >= maxi:\n",
    "                        maxi = stack[j][0]\n",
    "                        maxi_idx = stack[j][1]\n",
    "                while stack[0][1] < maxi_idx:\n",
    "                    stack.popleft()\n",
    "                res.append(stack[0][0])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        stack=[]\n",
    "        for i in range(k):\n",
    "            while(stack and stack[-1]<nums[i]):\n",
    "                stack.pop()\n",
    "            stack.append(nums[i])\n",
    "        res=[]\n",
    "        j=0\n",
    "        for i in range(k,n):\n",
    "            res.append(stack[0])\n",
    "            if nums[j]==stack[0]:\n",
    "                stack.pop(0)\n",
    "            while(stack and stack[-1]<nums[i]):\n",
    "                stack.pop()\n",
    "            stack.append(nums[i])\n",
    "            j+=1\n",
    "        res.append(stack[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        # n = len(nums)\n",
    "        # if n * k == 0:\n",
    "        #     return []\n",
    "        #\n",
    "        # return [max(nums[i:i + k]) for i in range(n - k + 1)]\n",
    "        from collections import deque\n",
    "        n = len(nums)\n",
    "        if n * k == 0:\n",
    "            return []\n",
    "        if k == 1:\n",
    "            return nums\n",
    "\n",
    "        def clean_dqueue(i):\n",
    "            # remove indexed of elements not from sliding window\n",
    "            if deq and deq[0] == i - k:\n",
    "                deq.popleft()\n",
    "\n",
    "            while deq and nums[i] > nums[deq[-1]]:\n",
    "                deq.pop()\n",
    "\n",
    "\n",
    "        deq = deque()\n",
    "        max_idx = 0\n",
    "        for i in range(k):\n",
    "            clean_dqueue(i)\n",
    "            deq.append(i)\n",
    "\n",
    "            if nums[i] > nums[max_idx]:\n",
    "                max_idx = i\n",
    "        output = [nums[max_idx]]\n",
    "\n",
    "        for i in range(k, n):\n",
    "            clean_dqueue(i)\n",
    "            deq.append(i)\n",
    "            output.append(nums[deq[0]])\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MyQueue:\n",
    "    def __init__(self):\n",
    "        self.queue=[]\n",
    "\n",
    "    def pop(self,value):\n",
    "         #不为空并且数值与队列出口相等才弹出，例如：num[i]=4,queue[0]=4,num[i]==queue[0],这个时候才弹出\n",
    "        if self.queue and value==self.queue[0]:\n",
    "            self.queue.pop(0)\n",
    "    \n",
    "    def push(self,value):\n",
    "       #列队不为空并且数值大于队列右面就弹出\n",
    "       #保持了从大到小的排列，例如queue=[3,-1,-3],value=5,5>-3,-3弹出，5>-1,-1弹出，5>3，3弹出，最后queue=[5]\n",
    "        while self.queue and value>self.queue[-1]:\n",
    "            self.queue.pop()\n",
    "        self.queue.append(value)\n",
    "    \n",
    "    def front(self):\n",
    "         #弹出之后剩下的就是从大到小排列，第一个就是最大值\n",
    "         return self.queue[0]\n",
    "class Solution:\n",
    "     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        que=MyQueue()\n",
    "        res=[]\n",
    "        for i in range(k): #先将前k的元素放进队列\n",
    "            que.push(nums[i])\n",
    "        res.append(que.front())\n",
    "        for i in range(k,len(nums)):\n",
    "            que.pop(nums[i-k])#滑动数组，把第一个元素剔除\n",
    "            que.push(nums[i])            \n",
    "            res.append(que.front())\n",
    "        return res\n",
    "\n",
    "# class MyQueue: #单调队列（从大到小\n",
    "#     def __init__(self):\n",
    "#         self.queue = [] #使用list来实现单调队列\n",
    "    \n",
    "#     #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。\n",
    "#     #同时pop之前判断队列当前是否为空。\n",
    "#     def pop(self, value):\n",
    "#         if self.queue and value == self.queue[0]:\n",
    "#             self.queue.pop(0)#list.pop()时间复杂度为O(n),这里可以使用collections.deque()\n",
    "            \n",
    "#     #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。\n",
    "#     #这样就保持了队列里的数值是单调从大到小的了。\n",
    "#     def push(self, value):\n",
    "#         while self.queue and value > self.queue[-1]:\n",
    "#             self.queue.pop()\n",
    "#         self.queue.append(value)\n",
    "        \n",
    "#     #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。\n",
    "#     def front(self):\n",
    "#         return self.queue[0]\n",
    "    \n",
    "# class Solution:\n",
    "#     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "#         que = MyQueue()\n",
    "#         result = []\n",
    "#         for i in range(k): #先将前k的元素放进队列\n",
    "#             que.push(nums[i])\n",
    "#         result.append(que.front()) #result 记录前k的元素的最大值\n",
    "#         for i in range(k, len(nums)):\n",
    "#             que.pop(nums[i - k]) #滑动窗口移除最前面元素\n",
    "#             que.push(nums[i]) #滑动窗口前加入最后面的元素\n",
    "#             result.append(que.front()) #记录对应的最大值\n",
    "#         return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        res = [0] * (n-k+1)\n",
    "        while left < n-k+1:\n",
    "            while right - left < k:\n",
    "                while stack and nums[stack[-1]] <= nums[right]:\n",
    "                    stack.pop()\n",
    "                stack.append(right)\n",
    "                right += 1\n",
    "            res[left] = nums[stack[0]]\n",
    "            if stack[0] == left:\n",
    "                stack.pop(0)\n",
    "            left += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        deque = collections.deque()\n",
    "        res, n = [], len(nums)\n",
    "        for i, j in zip(range(1 - k, n + 1 - k), range(n)):\n",
    "            # 删除 deque 中对应的 nums[i-1]\n",
    "            if i > 0 and deque[0] == nums[i - 1]:\n",
    "                deque.popleft()\n",
    "            # 保持 deque 递减\n",
    "            while deque and deque[-1] < nums[j]:\n",
    "                deque.pop()\n",
    "            deque.append(nums[j])\n",
    "            # 记录窗口最大值\n",
    "            if i >= 0:\n",
    "                res.append(deque[0])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MyQueue:\r\n",
    "\r\n",
    "    def __init__(self):\r\n",
    "        self.deque = []\r\n",
    "\r\n",
    "    def push(self, val):\r\n",
    "        while self.deque and self.deque[-1]<val:\r\n",
    "            self.deque.pop()\r\n",
    "        self.deque.append(val)\r\n",
    "\r\n",
    "    def pop(self, val):\r\n",
    "        if self.deque and self.deque[0] == val:\r\n",
    "            self.deque.pop(0)\r\n",
    "\r\n",
    "    def get_front(self):\r\n",
    "        return self.deque[0]\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\r\n",
    "        que = MyQueue()\r\n",
    "        list_max = []\r\n",
    "        for i in range(k):\r\n",
    "            que.push(nums[i])\r\n",
    "        list_max.append(que.get_front())\r\n",
    "\r\n",
    "        for i in range(k, len(nums)):\r\n",
    "            que.pop(nums[i-k])\r\n",
    "            que.push(nums[i])\r\n",
    "            list_max.append(que.get_front())\r\n",
    "        return list_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k == 1:\n",
    "            return nums\n",
    "        q = Queue()\n",
    "        i, j = 0, 0\n",
    "        while j < k:\n",
    "            q.add(nums[j])\n",
    "            j += 1\n",
    "        result = [q.de[0]]\n",
    "        j = k-1\n",
    "        while j < len(nums) - 1:\n",
    "            q.remove(nums[i])\n",
    "            i += 1\n",
    "            j += 1\n",
    "            q.add(nums[j])\n",
    "            result.append(q.de[0])\n",
    "        return result\n",
    "            \n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.de = deque()\n",
    "    def add(self, num):\n",
    "        while self.de and self.de[-1] < num:\n",
    "            self.de.pop()\n",
    "        self.de.append(num)\n",
    "    def remove(self, num):\n",
    "        if self.de[0] == num:\n",
    "            self.de.popleft()\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        N = len(nums)\n",
    "        results = [0] * (N-k+1)\n",
    "        queue = deque()\n",
    "        for i in range(N):\n",
    "            while len(queue) > 0 and nums[queue[-1]] <= nums[i]:\n",
    "                queue.pop()\n",
    "            queue.append(i)\n",
    "            if i >= k-1:\n",
    "                while len(queue) > 0 and queue[0] <= i - k:\n",
    "                    queue.popleft()\n",
    "                results[i - k + 1] = nums[queue[0]]\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        queue = deque()\n",
    "        # res = [0]*(len(nums)-k+1)\n",
    "        # res = []\n",
    "        for i in range(len(nums)):\n",
    "            if not queue:\n",
    "                queue.append(nums[i])\n",
    "            else:\n",
    "                while queue and nums[i] > queue[-1]:\n",
    "                    queue.pop()\n",
    "                queue.append(nums[i])\n",
    "            if i >= (k-1):\n",
    "                temp = queue[0]\n",
    "                if nums[i-k+1] == queue[0]:\n",
    "                    queue.popleft()\n",
    "                nums[i-k+1] = temp\n",
    "        return nums[0:len(nums)-k+1]\n",
    "\n",
    "# from collections import deque\n",
    "\n",
    "\n",
    "# class MyQueue: #单调队列（从大到小\n",
    "#     def __init__(self):\n",
    "#         self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时\n",
    "    \n",
    "#     #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。\n",
    "#     #同时pop之前判断队列当前是否为空。\n",
    "#     def pop(self, value):\n",
    "#         if self.queue and value == self.queue[0]:\n",
    "#             self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()\n",
    "            \n",
    "#     #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。\n",
    "#     #这样就保持了队列里的数值是单调从大到小的了。\n",
    "#     def push(self, value):\n",
    "#         while self.queue and value > self.queue[-1]:\n",
    "#             self.queue.pop()\n",
    "#         self.queue.append(value)\n",
    "        \n",
    "#     #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。\n",
    "#     def front(self):\n",
    "#         return self.queue[0]\n",
    "    \n",
    "# class Solution:\n",
    "#     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "#         que = MyQueue()\n",
    "#         result = []\n",
    "#         for i in range(k): #先将前k的元素放进队列\n",
    "#             que.push(nums[i])\n",
    "#         result.append(que.front()) #result 记录前k的元素的最大值\n",
    "#         for i in range(k, len(nums)):\n",
    "#             que.pop(nums[i - k]) #滑动窗口移除最前面元素\n",
    "#             que.push(nums[i]) #滑动窗口前加入最后面的元素\n",
    "#             result.append(que.front()) #记录对应的最大值\n",
    "#         return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\n",
    "# class Myqueue:\n",
    "#     def __init__(self):\n",
    "#         self.que = deque() # 初始化，一个双向队列\n",
    "\n",
    "#     def push(self, val): # 加入元素\n",
    "#         while self.que and val > self.que[-1]: # 比最后一个值大\n",
    "#             self.que.pop()\n",
    "#         self.que.append(val) # 前面没有比val更小的值，或者self.que为空了 则加入新元素\n",
    "\n",
    "#     def pop(self, val): # 移除元素\n",
    "#         if self.que and val == self.que[0]:\n",
    "#             self.que.popleft() # 如果队列不为空， 且要pop的值等于最左侧值的话，则pop掉左侧值\n",
    "\n",
    "#     def front(self): # 求最大元素\n",
    "#         return self.que[0] \n",
    "\n",
    "# class Solution:\n",
    "#     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "#         que = Myqueue() # 初始化类\n",
    "#         res = [] # 保存结果\n",
    "#         for i in range(k): # 前k个元素\n",
    "#             que.push(nums[i]) # 加入元素\n",
    "#         res.append(que.front()) # 保存最大值元素\n",
    "\n",
    "#         # 移动窗口\n",
    "#         for i in range(k, len(nums)):\n",
    "#             que.pop(nums[i-k]) # 删除最左侧元素\n",
    "#             que.push(nums[i]) # 加入最新元素\n",
    "#             res.append(que.front()) # 记录最大元素\n",
    "#         return res\n",
    "\n",
    "class Myqueque:\n",
    "    def __init__(self):\n",
    "        self.que = deque() # 初始化\n",
    "    def push(self, val):\n",
    "        while self.que and val > self.que[-1]:\n",
    "            self.que.pop()\n",
    "        self.que.append(val) \n",
    "    def pop(self, val):\n",
    "        if val == self.que[0]:\n",
    "            self.que.popleft()\n",
    "    def front(self):\n",
    "        return self.que[0]\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:\n",
    "        re = Myqueque()\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            re.push(nums[i])\n",
    "        res.append(re.front())\n",
    "        for i in range(k, len(nums)):\n",
    "            re.pop(nums[i-k])\n",
    "            re.push(nums[i])\n",
    "            res.append(re.front())\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "        queue = []\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            if queue and queue[0]+k == i: \n",
    "                # 当前最大值已经 不属于当前窗口了\n",
    "                queue.pop(0)\n",
    "            while queue and nums[queue[-1]] < nums[i]:\n",
    "                queue.pop()\n",
    "            queue.append(i)\n",
    "            if i>=k-1:\n",
    "                res.append(nums[queue[0]])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        i = 0\n",
    "        max_list = collections.deque()\n",
    "        res = []\n",
    "        while i < len(nums):\n",
    "            while max_list and max_list[-1] < nums[i]: max_list.pop()\n",
    "            max_list.append(nums[i])\n",
    "            if i >= k - 1:\n",
    "                res.append(max_list[0])\n",
    "                if nums[i - k + 1] == max_list[0]: max_list.popleft()\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        result = []\n",
    "        window = deque()\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            # 在插入新元素前，确保队列中元素是递减的\n",
    "            while window and nums[i] > nums[window[-1]]:\n",
    "                window.pop()\n",
    "\n",
    "            # 插入当前元素的下标\n",
    "            window.append(i)\n",
    "\n",
    "            # 如果队首元素不在当前滑动窗口中，将其移除\n",
    "            if window[0] < i - k + 1:\n",
    "                window.popleft()\n",
    "\n",
    "            # 当滑动窗口达到大小 k 时，记录当前最大值\n",
    "            if i >= k - 1:\n",
    "                result.append(nums[window[0]])\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MyQueue:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.queue = deque()\n",
    "    \n",
    "    def pop(self, val):\n",
    "        if self.queue and val == self.queue[0]:\n",
    "            self.queue.popleft()\n",
    "    def push(self, val):\n",
    "        while self.queue and val > self.queue[-1]:\n",
    "            self.queue.pop()\n",
    "        self.queue.append(val)\n",
    "\n",
    "    def front(self):\n",
    "        return self.queue[0]\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        q = MyQueue()\n",
    "        ans = []\n",
    "\n",
    "        for i in range(k):\n",
    "            q.push(nums[i])\n",
    "        ans.append(q.front())\n",
    "        for i in range(k, len(nums)):\n",
    "            q.pop(nums[i-k])\n",
    "            q.push(nums[i])\n",
    "            ans.append(q.front())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        #单调栈，元素后面存在比前面大的，前面的直接不要，比前面小的，进栈，保证栈顶是最大元素\n",
    "        stk = collections.deque()\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        for i in range(k):\n",
    "            while stk and stk[-1][1] < nums[i]:\n",
    "                stk.pop()\n",
    "            stk.append((i, nums[i]))\n",
    "        for i in range(1, n - k + 1):\n",
    "            res.append(stk[0][1])\n",
    "            #分别是要丢的以及要加入的索引\n",
    "            left = i - 1\n",
    "            right = i + k - 1\n",
    "            if stk[0][0] == left:\n",
    "                stk.popleft()\n",
    "            while stk and stk[-1][1] < nums[right]:\n",
    "                stk.pop()\n",
    "            stk.append((right, nums[right]))\n",
    "        res.append(stk[0][1])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        from collections import deque\n",
    "        queue: deque[tuple[int, int]] = deque()\n",
    "        ans: list[int] = []\n",
    "        for index, num in enumerate(nums):\n",
    "            while queue and queue[0][1] <= index - k:\n",
    "                queue.popleft()\n",
    "            while queue and queue[-1][0] < num:\n",
    "                queue.pop()\n",
    "            queue.append((num, index))\n",
    "            ans.append(queue[0][0])\n",
    "        return ans[k - 1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n \n",
    "        s = []\n",
    "        for i, j in enumerate(nums):\n",
    "            while s and nums[s[-1]] <= j:\n",
    "                right[s.pop()] = i \n",
    "            if s:\n",
    "                left[i] = s[-1]\n",
    "            s.append(i)\n",
    "        ans = [-inf] * (n - k + 1)\n",
    "        for i in range(n):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            if r - l + 1 >= k:\n",
    "                for start in range(max(l, i - k + 1), min(i, r - k + 1) + 1):\n",
    "                    ans[start] = nums[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []  # idx, num\n",
    "        for i in range(k - 1):\n",
    "            while stack and stack[-1][1] < nums[i]:\n",
    "                stack.pop()\n",
    "            stack.append([i, nums[i]])\n",
    "        ans = []\n",
    "        for j in range(k - 1, n):\n",
    "            while stack and stack[-1][1] < nums[j]:\n",
    "                stack.pop()\n",
    "            stack.append([j, nums[j]])\n",
    "            ans.append(stack[0][1])\n",
    "            while stack and stack[0][0] <= j - k + 1:\n",
    "                stack.pop(0)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        num_idx = dict()\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            start = i-k+1\n",
    "            if start>=0:\n",
    "                while(len(heap) > 0 and num_idx[heap[0]]<start and heap[0]<-nums[i]):\n",
    "                    del num_idx[heapq.heappop(heap)]\n",
    "            if len(heap) == 0 or -nums[i] <= heap[0]:\n",
    "                heap = [-nums[i]]\n",
    "                num_idx = dict()\n",
    "            elif -nums[i] not in num_idx:\n",
    "                heapq.heappush(heap, -nums[i])\n",
    "            num_idx[-nums[i]] = i\n",
    "            if start>=0:\n",
    "                res.append(-heap[0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        暴力法：O(nk) 遍历一遍，每次在k个数中找到最大值，肯定是不行的\n",
    "        只找最大值感觉可以整个堆\n",
    "\n",
    "        toDelete 是一个懒惰标记，等需要pop它的时候就pop掉\n",
    "        答案写的简洁一点，每次都将 left 的元素pop掉\n",
    "        \"\"\"\n",
    "        left, right = 0, 0\n",
    "        ret = []\n",
    "        heap = []\n",
    "        toDelete = defaultdict(int)\n",
    "\n",
    "        for i in range(k):\n",
    "            right = i\n",
    "            if right < len(nums):\n",
    "                heapq.heappush(heap, -nums[right])\n",
    "        while right < len(nums):\n",
    "            ret.append(-heap[0])\n",
    "            toDelete[-nums[left]] += 1\n",
    "            while heap and heap[0] in toDelete and toDelete[heap[0]] > 0: \n",
    "                toDelete[heap[0]] -= 1\n",
    "                heapq.heappop(heap)\n",
    "            left+=1\n",
    "            right+=1\n",
    "            if right < len(nums):\n",
    "                heapq.heappush(heap, -nums[right])\n",
    "            i += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        \"\"\" 延迟删除 heap priority queue 类似 480 题 或者 218 题\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        end = n - k\n",
    "        res = []\n",
    "        heap = []\n",
    "        delay_remove = defaultdict(int)\n",
    "        for window_start in range(end + 1):\n",
    "            window_end = window_start + k - 1\n",
    "            if window_start == 0:\n",
    "                for i in range(window_end + 1):\n",
    "                    heapq.heappush(heap, -nums[i])\n",
    "            else:\n",
    "                # 直接删除\n",
    "                # heap.remove(-nums[window_start - 1])\n",
    "                # heapq.heapify(heap)\n",
    "                # 延迟删除：\n",
    "                to_remove = -nums[window_start - 1]\n",
    "                delay_remove[to_remove] += 1\n",
    "                while heap and delay_remove.get(heap[0], 0) > 0:\n",
    "                    delay_remove[heap[0]] -= 1\n",
    "                    heapq.heappop(heap)\n",
    "                heapq.heappush(heap, -nums[window_end])\n",
    "            res.append(-heap[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "\n",
    "        def adjust_heap(nums, i, n):  # recursive\n",
    "            root = i\n",
    "            l, r = root*2+1, root*2+2\n",
    "            if l < n:\n",
    "                if r >= n or nums[l][0] > nums[r][0]:\n",
    "                    max_son = l\n",
    "                else:\n",
    "                    max_son = r\n",
    "\n",
    "                if nums[max_son][0] > nums[root][0]:\n",
    "                    nums[max_son], nums[root] = nums[root], nums[max_son]\n",
    "                    adjust_heap(nums, max_son, n)\n",
    "\n",
    "        def build_heap(nums):\n",
    "            n = len(nums)\n",
    "            for i in range((n-1)//2, -1, -1):\n",
    "                adjust_heap(nums, i, n)\n",
    "\n",
    "        def heap_add(nums, new_item, i, n):\n",
    "            nums.append(new_item)\n",
    "            son = n\n",
    "            while (son-1)//2 >= 0:\n",
    "                father = (son-1)//2\n",
    "                if nums[father][0] < nums[son][0]:\n",
    "                    nums[father], nums[son] = nums[son], nums[father]\n",
    "                    son = father\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        def heap_remove(nums, i, n):\n",
    "            nums[i], nums[n-1] = nums[n-1], nums[i]\n",
    "            nums.pop()\n",
    "            adjust_heap(nums, 0, n-1)\n",
    "\n",
    "        nums_copy = []\n",
    "        for i in range(k):\n",
    "            nums_copy.append([nums[i], i])\n",
    "\n",
    "        build_heap(nums_copy)\n",
    "\n",
    "        res = [nums_copy[0][0]]\n",
    "        for i in range(k, n):\n",
    "            heap_add(nums_copy, [nums[i], i], 0, len(nums_copy))\n",
    "            while nums_copy[0][1] <= i-k:\n",
    "                heap_remove(nums_copy, 0, len(nums_copy))\n",
    "            res.append(nums_copy[0][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "\n",
    "        def adjust_heap(nums, i, n):  # recursive\n",
    "            root = i\n",
    "            l, r = root*2+1, root*2+2\n",
    "            if l < n:\n",
    "                if r >= n or nums[l][0] > nums[r][0]:\n",
    "                    max_son = l\n",
    "                else:\n",
    "                    max_son = r\n",
    "\n",
    "                if nums[max_son][0] > nums[root][0]:\n",
    "                    nums[max_son], nums[root] = nums[root], nums[max_son]\n",
    "                    adjust_heap(nums, max_son, n)\n",
    "\n",
    "        def build_heap(nums):\n",
    "            n = len(nums)\n",
    "            for i in range((n-1)//2, -1, -1):\n",
    "                adjust_heap(nums, i, n)\n",
    "\n",
    "        def heap_add(nums, new_item, i, n):\n",
    "            nums.append(new_item)\n",
    "            son = n\n",
    "            while (son-1)//2 >= 0:\n",
    "                father = (son-1)//2\n",
    "                if nums[father][0] < nums[son][0]:\n",
    "                    nums[father], nums[son] = nums[son], nums[father]\n",
    "                    son = father\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        def heap_remove(nums, i, n):\n",
    "            nums[i], nums[n-1] = nums[n-1], nums[i]\n",
    "            nums.pop()\n",
    "            adjust_heap(nums, 0, n-1)\n",
    "\n",
    "        nums_copy = []\n",
    "        for i in range(k):\n",
    "            nums_copy.append([nums[i], i])\n",
    "\n",
    "        build_heap(nums_copy)\n",
    "\n",
    "        res = [nums_copy[0][0]]\n",
    "        for i in range(k, n):\n",
    "            heap_add(nums_copy, [nums[i], i], 0, len(nums_copy))\n",
    "            while nums_copy[0][1] <= i-k:\n",
    "                heap_remove(nums_copy, 0, len(nums_copy))\n",
    "            res.append(nums_copy[0][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        nums = [-i for i in nums]\n",
    "        nums_w = nums[:k]\n",
    "        heapify(nums_w)\n",
    "        nums2r = []\n",
    "        ret = []\n",
    "        for n_idx in range(k, len(nums)):\n",
    "            while True:\n",
    "                n = nums_w[0]\n",
    "                if nums2r and nums2r[0] == n:\n",
    "                    heappop(nums_w)\n",
    "                    heappop(nums2r)\n",
    "                    continue\n",
    "                else:\n",
    "                    ret.append(-n)\n",
    "                    break\n",
    "            \n",
    "            \n",
    "            n = nums[n_idx]\n",
    "            heappush(nums_w, n)\n",
    "            heappush(nums2r, nums[n_idx - k])\n",
    "        \n",
    "        while True:\n",
    "            n = nums_w[0]\n",
    "            if nums2r and nums2r[0] == n:\n",
    "                heappop(nums_w)\n",
    "                heappop(nums2r)\n",
    "                continue\n",
    "            else:\n",
    "                ret.append(-n)\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if len(nums)==1 or k==1:return nums\n",
    "        qstack=[(0,nums[0])]\n",
    "        head=0\n",
    "        res=[]\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            # pop left \n",
    "            while qstack[head][0]<=i-k:\n",
    "                    head +=1 \n",
    "            # push right\n",
    "            tail = len(qstack)-1\n",
    "            current = nums[i]\n",
    "            while tail >=head  and current >qstack[tail][1]:\n",
    "                qstack.pop()\n",
    "                tail-=1\n",
    "            qstack.append((i,current))\n",
    "            if i>=k-1: # print res \n",
    "                res.append(qstack[head][1])\n",
    "\n",
    "            #print(i,nums[i],':',qstack[head:],res)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        max_value = nums[0]\n",
    "        max_index = 0\n",
    "        list_length = len(nums)\n",
    "        if list_length < k: return []\n",
    "        result = []\n",
    "        queue = PriorityQueue()\n",
    "        for i in range(k):\n",
    "            queue.put((-nums[i], i))\n",
    "        element = queue.get()\n",
    "        max_value = -element[0]\n",
    "        max_index = element[1]\n",
    "\n",
    "        result.append(max_value)\n",
    "        for i in range(1, list_length - k + 1):\n",
    "            queue.put((-nums[i + k - 1], i + k - 1))\n",
    "            if nums[i + k - 1] > max_value:\n",
    "                max_value = nums[i + k - 1]\n",
    "                max_index = k - 1\n",
    "            else:\n",
    "                max_index = max_index - 1\n",
    "            if max_index < 0:\n",
    "                element = queue.get()\n",
    "                while element[1] < i:\n",
    "                    element = queue.get()\n",
    "                max_value = -element[0]\n",
    "                max_index = element[1] - i\n",
    "            result.append(max_value)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k == 1: return nums\n",
    "        dps, ans = [], []\n",
    "        for i, num in enumerate(nums[:k - 1]):\n",
    "            heappush(dps, (-num, i))\n",
    "        for i, num in enumerate(nums[k - 1:], k - 1):\n",
    "            if num >= -dps[0][0]: dps = [(-num, i)]\n",
    "            else: heappush(dps, (-num, i))\n",
    "            while dps[0][1] <= i - k: heappop(dps)\n",
    "            ans.append(-dps[0][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import asyncio\n",
    "import base64\n",
    "import copy\n",
    "import html\n",
    "import io\n",
    "import json\n",
    "import os\n",
    "import pickle\n",
    "import random\n",
    "import re\n",
    "import shelve\n",
    "import sqlite3\n",
    "import sys\n",
    "import time\n",
    "from collections import OrderedDict\n",
    "from cProfile import label\n",
    "from datetime import datetime\n",
    "from io import BytesIO\n",
    "from unittest.mock import call\n",
    "from urllib import request\n",
    "from typing import Union\n",
    "\n",
    "def c_ar(i,j):\n",
    "    if not j:\n",
    "        return [0 for _ in range(i)]\n",
    "    else:\n",
    "        return [[0 for _ in range(j)] for _ in range(i)]\n",
    "\n",
    "def st_d(n):\n",
    "    return sorted(n,lambda x:x[1])\n",
    "\n",
    "def re_d(n):\n",
    "    return sorted(n,lambda x:x[1],True)\n",
    "\n",
    "def max_(i,j):\n",
    "    if i > j:\n",
    "        return i\n",
    "    else:\n",
    "        return j\n",
    "\n",
    "def min_(i,j):\n",
    "    if i > j:\n",
    "        return j\n",
    "    else:\n",
    "        return i\n",
    "\n",
    "def fp():\n",
    "    with open(\"C:\\\\user\\\\bingyue\\\\desktop\\\\1.txt\",\"w+\") as f:\n",
    "        f.close()\n",
    "\n",
    "def fw(t):\n",
    "    with open(\"C:\\\\user\\\\bingyue\\\\desktop\\\\1.txt\",\"w+\") as f:\n",
    "        f.write(t)\n",
    "        f.close()\n",
    "\n",
    "def about():\n",
    "    print(\"冰月博客:<https://blog.bingyue.top>\")\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def searchPrefix(self, prefix: str) -> \"Trie\":\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                return None\n",
    "            node = node.children[ch]\n",
    "        return node\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self.searchPrefix(word)\n",
    "        return node is not None and node.isEnd\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        return self.searchPrefix(prefix) is not None\n",
    "\n",
    "about()\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        d = c_ar(len(nums)-k+1,0)\n",
    "        st = deque();j=0;i=0\n",
    "        while j < len(nums):\n",
    "            n = nums[j]\n",
    "            while st and nums[st[-1]] < n:\n",
    "                st.pop()\n",
    "            st.append(j)\n",
    "            if j >= k-1:\n",
    "                d[i]=nums[st[0]]\n",
    "                if i == st[0]:\n",
    "                    st.popleft()\n",
    "                i+=1\n",
    "            j+=1\n",
    "        return d "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import asyncio\n",
    "import base64\n",
    "import copy\n",
    "import html\n",
    "import io\n",
    "import json\n",
    "import os\n",
    "import pickle\n",
    "import random\n",
    "import re\n",
    "import shelve\n",
    "import sqlite3\n",
    "import sys\n",
    "import time\n",
    "from collections import OrderedDict\n",
    "from cProfile import label\n",
    "from datetime import datetime\n",
    "from io import BytesIO\n",
    "from unittest.mock import call\n",
    "from urllib import request\n",
    "from typing import Union\n",
    "\n",
    "def c_ar(i,j):\n",
    "    if not j:\n",
    "        return [0 for _ in range(i)]\n",
    "    else:\n",
    "        return [[0 for _ in range(j)] for _ in range(i)]\n",
    "\n",
    "def st_d(n):\n",
    "    return sorted(n,lambda x:x[1])\n",
    "\n",
    "def re_d(n):\n",
    "    return sorted(n,lambda x:x[1],True)\n",
    "\n",
    "def max_(i,j):\n",
    "    if i > j:\n",
    "        return i\n",
    "    else:\n",
    "        return j\n",
    "\n",
    "def min_(i,j):\n",
    "    if i > j:\n",
    "        return j\n",
    "    else:\n",
    "        return i\n",
    "\n",
    "def fp():\n",
    "    with open(\"C:\\\\user\\\\bingyue\\\\desktop\\\\1.txt\",\"w+\") as f:\n",
    "        f.close()\n",
    "\n",
    "def fw(t):\n",
    "    with open(\"C:\\\\user\\\\bingyue\\\\desktop\\\\1.txt\",\"w+\") as f:\n",
    "        f.write(t)\n",
    "        f.close()\n",
    "\n",
    "def about():\n",
    "    print(\"冰月博客:<https://blog.bingyue.top>\")\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def searchPrefix(self, prefix: str) -> \"Trie\":\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                return None\n",
    "            node = node.children[ch]\n",
    "        return node\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self.searchPrefix(word)\n",
    "        return node is not None and node.isEnd\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        return self.searchPrefix(prefix) is not None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        d = c_ar(len(nums)-k+1,0)\n",
    "        st = deque();j=0;i=0\n",
    "        while j < len(nums):\n",
    "            n = nums[j]\n",
    "            while st and nums[st[-1]] < n:\n",
    "                st.pop()\n",
    "            st.append(j)\n",
    "            if j >= k-1:\n",
    "                d[i]=nums[st[0]]\n",
    "                if i == st[0]:\n",
    "                    st.popleft()\n",
    "                i+=1\n",
    "            j+=1\n",
    "        return d "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        for i in range(n):nums[i]=-nums[i]\n",
    "\n",
    "        h=[]\n",
    "        for i in range(k):heapq.heappush(h, (nums[i], i))\n",
    "        \n",
    "        res=[-h[0][0]]\n",
    "\n",
    "        for i in range(k,n):\n",
    "            heapq.heappush(h, (nums[i], i))\n",
    "            while h[0][1]<=i-k:\n",
    "                heapq.heappop(h)\n",
    "            res.append(-h[0][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        for i in range(n):nums[i]=-nums[i]\n",
    "\n",
    "        h=[]\n",
    "        for i in range(k):heapq.heappush(h, (nums[i], i))\n",
    "        \n",
    "        res=[-h[0][0]]\n",
    "\n",
    "        for i in range(k,n):\n",
    "            heapq.heappush(h, (nums[i], i))\n",
    "            while h[0][1]<=i-k:\n",
    "                heapq.heappop(h)\n",
    "            res.append(-h[0][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q = [(-nums[i], i) for i in range(k)]\n",
    "        heapq.heapify(q)\n",
    "\n",
    "        ans = [-q[0][0]]\n",
    "        for i in range(k, n):\n",
    "            heapq.heappush(q, (-nums[i], i))\n",
    "            while q[0][1] <= i - k:\n",
    "                heapq.heappop(q)\n",
    "            ans.append(-q[0][0])\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
